/**
 * 复原 ip 地址
 *
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组
 * 成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
 * 但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所
 * 有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.'
 * 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 *
 * 示例 1：
 * 输入：s = "25525511135"
 * 输出：["255.255.11.135","255.255.111.35"]
 * 示例 2：
 * 输入：s = "0000"
 * 输出：["0.0.0.0"]
 * 示例 3：
 * 输入：s = "101023"
 * 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 *
 * 提示：
 * 1 <= s.length <= 20
 * s 仅由数字组成
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 这我们用递归回溯来写, 每个数字作为开头要遍历 3 次, 因为最大是 255, 也就是三位数
 * 这里我们循环处理三位数, 当然在最后面的时候位数可能是小于三位的, 这个时候我们要特别
 * 判断一下, 然后就是正常递归
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 全局变量
    List<String> list;
    StringBuffer ret;
    int n;

    public List<String> restoreIpAddresses(String s) {

        // 初始化
        list = new ArrayList<>();
        ret = new StringBuffer();
        n = s.length();

        // 递归
        dfs(s, 0, 0);

        // 返回结果
        return list;
    }

    public void dfs(String s, int k, int i) {

        // 这里不仅要 4 次, 还需要总的长度加上没去的 . 比原来大 4
        if (k == 4 && ret.length() - 4 == n) {

            // 这里加入的时候要及得去除最后一个 . , 但是在 ret 中是不能去除的, 因为
            // 最后的. 我们是在后面的循环中去除的
            list.add(ret.toString().substring(0, ret.length() - 1));
            return;
        }

        // 这里因为上面有两个条件, 所以这里还要继续判断一下
        if (k >= 4) {
            return;
        }

        // 这里避免最后一次总长度没 3, 避免越界
        int tmp = n - i;
        if (tmp > 3) {
            tmp = 3;
        }

        for (int j = 1; j <= tmp; j++) {

            // 防止出现前导零
            if (j == 2 && s.charAt(i) == '0'
                    || j == 3 && s.charAt(i) == '0' && s.charAt(i + 1) == '0') {
                break;
            }

            // 这里先记录下字符, 判断数字是否在范围内
            StringBuffer str = new StringBuffer();
            for (int q = 0; q < j; q++) {
                str.append(s.charAt(i + q));
            }

            // 判断范围
            if (Integer.parseInt(str.toString()) > 255) {
                break;
            } else {
                ret.append(str);
            }

            // 这里别忘记加上 .
            ret.append('.');

            // 递归
            dfs(s, k + 1, i + j);

            // 回溯, 恢复现场
            for (int q = 0; q <= j; q++) {
                ret.deleteCharAt(ret.length() - 1);
            }
        }
    }

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        test.restoreIpAddresses("101023");
    }
}